package practise.alogrithm.hundredInterviewQuestions.convertToConcurrent;

import practise.alogrithm.hundredInterviewQuestions.Utils.TreeBuilder;
import practise.alogrithm.hundredInterviewQuestions.Utils.TreeNode;

import java.util.concurrent.*;

/**
 * Created by richard on 6/16/14.
 */
public class ConvertTreeToBidirectionLink extends RecursiveTask<TreeNode> {
    private TreeNode indexNode, rootNode;

    public ConvertTreeToBidirectionLink(TreeNode indexNode, TreeNode rootNode) {
        this.indexNode = indexNode;
        this.rootNode = rootNode;
    }

    @Override
    protected TreeNode compute() {
       if(rootNode.getLeft()==null && rootNode.getRight()==null){
           if(indexNode.getLeft()==null){
               indexNode.setLeft(rootNode);
               indexNode.setRight(rootNode);
           }
           joinNodes(indexNode, rootNode);
           return indexNode.getRight();
       }

        ConvertTreeToBidirectionLink convertLeft = new ConvertTreeToBidirectionLink(indexNode,rootNode.getLeft());
        ConvertTreeToBidirectionLink convertRight = new ConvertTreeToBidirectionLink(indexNode,rootNode.getRight());

        convertLeft.fork();
        TreeNode leftNode = convertLeft.join();
        joinNodes(indexNode,leftNode);

        joinNodes(indexNode, rootNode);

        convertRight.fork();
        TreeNode rightNode = convertRight.join();
        joinNodes(indexNode,rightNode);


        return indexNode.getRight();
    }

    private void joinNodes(TreeNode indexNode, TreeNode current) {
        if(current!=indexNode.getRight())// avoid a dead loop for the first node
            current.setLeft(indexNode.getRight());
        indexNode.getRight().setRight(current);
        indexNode.setRight(current);
        indexNode.getRight().setRight(null);

    }

    public static void main(String[] args) {


        TreeNode treeNode = TreeBuilder.buildTree();
        TreeNode head = new TreeNode();
        ConvertTreeToBidirectionLink convertTreeToBidirectionLink = new ConvertTreeToBidirectionLink(head, treeNode);
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        Future<TreeNode> future = forkJoinPool.submit(convertTreeToBidirectionLink);
        forkJoinPool.awaitQuiescence(1000, TimeUnit.SECONDS);

        TreeNode result = null;
        try {
            result = future.get();
            result = head.getLeft();
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        }
       do {
            System.out.print(result.getValue() + "==>");
            if (result.getRight() != null)
                result = result.getRight();
        } while (result.getRight() != null);

        System.out.println();
        result = head.getRight();
        while (result.getLeft() != null) {
            System.out.print(result.getValue() + "<==");
            result = result.getLeft();
        }

    }
}
